package lanqiao;
/**
 * @Project : AlgorithmLearning
 * @Package : LanQiao.PrepareForCompetition
 * @File : Q0132.java
 * @Author : WangRuoyu
 * @Date : 2023/3/25 11:55
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q0132 {

    static final long MOD = 1000000007;
    static final int N = 6;
    static int n;
    static int m;

    static int getOps(int x) {
        if (x > 3) {
            return x - 3;
        } else {
            return x + 3;
        }
    }

    static void mul(long[][] a, long[][] b) {
        long[][] tmp = new long[N][N];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                for (int k = 0; k < N; ++k) {
                    tmp[i][j] = (tmp[i][j] + (a[i][k] * b[k][j])) % MOD;
                }
            }
        }
        for (int i = 0; i < N; ++i) {
            System.arraycopy(tmp[i], 0, a[i], 0, N);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] words = br.readLine().split(" ");

        long[][] A = new long[N][N];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                A[i][j] = 4;
            }
        }

        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);

        for (int i = 0; i < m; ++i) {
            words = br.readLine().split(" ");
            int a = Integer.parseInt(words[0]);
            int b = Integer.parseInt(words[1]);
            A[a - 1][getOps(b) - 1] = 0;
            A[b - 1][getOps(a) - 1] = 0;
        }

        long[][] f = {{4, 4, 4, 4, 4, 4}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}};

        for (int k = n - 1; k > 0; k >>= 1) {
            if ((k & 1) == 1) mul(f, A);
            mul(A, A);
        }

        long res = 0;
        for (int i = 0; i < N; ++i) {
            res = (res + f[0][i]) % MOD;
        }
        System.out.println(res);
    }
}